//class Solution {
//public:
//    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums1.size();
//        int m = nums2.size();
//        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (nums1[i - 1] == nums2[j - 1])
//                {
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }
//                else
//                {
//                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//                }
//            }
//        }
//        return dp[n][m];
//    }
//};

//class Solution {
//public:
//    int numDistinct(string s, string t) {
//        int m = t.size();
//        int n = s.size();
//        vector<vector<double>> dp(m + 1, vector<double>(n + 1));
//        for (int i = 0; i <= n; i++)
//        {
//            dp[0][i] = 1;
//        }
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] += dp[i][j - 1];
//                if (t[i - 1] == s[j - 1]) dp[i][j] += dp[i - 1][j - 1];
//            }
//        }
//        return dp[m][n];
//    }
//};

//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int m = s.size();
//        int n = p.size();
//        s = " " + s;
//        p = " " + p;
//        //
//        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
//        dp[0][0] = true;
//        for (int j = 1; j <= n; j++)
//        {
//            if (p[j] == '*')
//            {
//                dp[0][j] = true;
//            }
//            else break;
//        }
//        //
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                if (p[j] == '*')
//                {
//                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
//                }
//                else
//                {
//                    dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];
//                }
//            }
//        }
//        return dp[m][n];
//    }
//};


//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int m = s.size(), n = p.size();
//        s = ' ' + s;
//        p = ' ' + p;
//        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
//        dp[0][0] = true;
//        for (int i = 2; i <= n; i += 2)
//        {
//            if (p[i] == '*')
//                dp[0][i] = true;
//            else break;
//        }
//        //
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                if (p[j] == '*')
//                {
//                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
//                }
//                else
//                {
//                    dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
//                }
//            }
//        }
//        return dp[m][n];
//    }
//};


//class Solution {
//public:
//    bool isInterleave(string s1, string s2, string s3) {
//        int m = s1.size();
//        int n = s2.size();
//        if (s3.size() != m + n) return false;
//        s1 = ' ' + s1;
//        s2 = ' ' + s2;
//        s3 = ' ' + s3;
//        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
//        dp[0][0] = true;
//        for (int j = 1; j <= n; j++)
//        {
//            if (s2[j] == s3[j]) dp[0][j] = true;
//            else break;
//        }
//        for (int i = 1; i <= m; i++)
//        {
//            if (s1[i] == s3[i]) dp[i][0] = true;
//            else break;
//        }
//        //
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]);
//            }
//        }
//        return dp[m][n];
//    }
//};


//class Solution {
//public:
//    int minimumDeleteSum(string s1, string s2) {
//        int m = s1.size(), n = s2.size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//                if (s1[i - 1] == s2[j - 1])
//                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
//            }
//        }
//        int ret = 0;
//        for (auto e : s1) ret += e;
//        for (auto e : s2) ret += e;
//        return ret - dp[m][n] * 2;
//    }
//};

//class Solution {
//public:
//    int findLength(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums1.size();
//        int m = nums2.size();
//        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//        int ret = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (nums1[i - 1] == nums2[j - 1])
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                ret = max(ret, dp[i][j]);
//            }
//        }
//        return ret;
//    }
//};

